/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <queue> 
#include <stack>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit_arr(vector<int>& arr, string const str){
    vector<int>::iterator it;
    cout << str << ": ";
    for(it=arr.begin();it!=arr.end();++it){
        cout << *it <<" ";
    }
    cout<<endl;
}
// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit2_arr(vector<int>& arr, string const str){
    cout << str << ": ";
    for(int i; i < arr.size(); ++i){
        cout << arr[i] << " ";
    }
    cout<<endl;
}



// 链表结点
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void visit_list(ListNode* head){
    ListNode* tmp = head;
    while(tmp != nullptr){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << endl;
}

// 二叉树--孩子兄弟表示法
//Definition for a binary tree node.// 二叉树--孩子兄弟表示法
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/**
 * 我用的应该是计数排序的原理，O(n)时间复杂度吧
 * 文字比较枯燥，我们来看下一个实例吧。
 * 假设原始数组 nums = [1,5,10,6,2,8]
 * 可以很轻松就能获取到最大的分值是10，所以我们申请一个数组nums_index，元素全是-1，长度为11（即：max+1）
 * nums_index = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
 * 接下来我们操作nums_index，把原始数组nums里每个元素的值当做nums_index的下标，并把该下标处的值置为原始数组的下标。额...有点绕，继续往下看就明白了。
 * 操作完后的nums_index长这样
 * nums_index = [0, -1, 4, -1, -1, 1, 3, -1, 5, -1, 2]
 * 解释下nums_index，我们从最后面往前看≥0的值
 * 第一名在原始数组下标2的位置
 * 第二名在原始数组下标5的位置
 * 第三名在原始数组下标3的位置
 * 第四名在原始数组下标1的位置
 * 第五名在原始数组下标4的位置
 * 第六名在原始数组下标0的位置
*/
class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        vector<int> t=score;
        map<int,int> m2;
        vector<string> res;
        sort(score.begin(),score.end(),greater<int>());
        for(int i=0;i<score.size();i++)
            m2[score[i]]=i;
        for(int i=0;i<t.size();i++){
            if(m2[t[i]]==0)
                res.push_back("Gold Medal");
            else if(m2[t[i]]==1)
                res.push_back("Silver Medal");
            else if(m2[t[i]]==2)
                res.push_back("Bronze Medal");
            else 
                res.push_back(to_string(m2[t[i]]+1));
        }
        return res;
    }
};


int main(int argc, const char** argv) {
    Solution solu = Solution();
    vector<int> score = {5, 4, 3, 2, 1};
    vector<string> ans = solu.findRelativeRanks(score);

    for(auto it=ans.begin();it!=ans.end();++it){
        cout << *it <<" ";
    }
    cout<<endl;
    return 0;
}